home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group98a.txt / 000131_icon-group-sender _Fri Mar 13 12:35:20 1998.msg < prev    next >
Internet Message Format  |  2000-09-20  |  3KB
  1. Return-Path: <icon-group-sender>
  2. Received: from kingfisher.CS.Arizona.EDU (kingfisher.CS.Arizona.EDU [192.12.69.239])
  3.     by baskerville.CS.Arizona.EDU (8.8.7/8.8.7) with SMTP id MAA14412
  4.     for <icon-group-addresses@baskerville.CS.Arizona.EDU>; Fri, 13 Mar 1998 12:35:20 -0700 (MST)
  5. Received: by kingfisher.CS.Arizona.EDU (5.65v4.0/1.1.8.2/08Nov94-0446PM)
  6.     id AA15665; Fri, 13 Mar 1998 12:35:19 -0700
  7. From: eka@corp.cirrus.com (Eka Laiman)
  8. Message-Id: <199803131831.KAA01976@sims-rd.corp.cirrus.com>
  9. Subject: Re: Letter Probabilities
  10. To: evans@gte.net
  11. Date: Fri, 13 Mar 1998 10:27:42 -0800 (PST)
  12. Cc: icon-group@optima.CS.Arizona.EDU
  13. In-Reply-To: <35089F74.6018@gte.net> from "Mark Evans" at Mar 12, 98 08:52:36 pm
  14. X-Mailer: ELM [version 2.4 PL24alpha3]
  15. Mime-Version: 1.0
  16. Content-Type: text/plain; charset=US-ASCII
  17. Content-Transfer-Encoding: 7bit
  18. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  19. Status: RO
  20. Content-Length: 1684
  21.  
  22. Mark Evans wrote:
  23. > Here is a small Icon problem related to letter probabilites.  Each
  24. > letter has a "probability of occurrence" in the information-theoretic
  25. > setting.  This probability can be estimated from sample texts.  I want
  26. > to generate random text based on these probabilities.
  27. > ............... rest is removed .........
  28.  
  29. This is what I would do:
  30.  
  31. (1) Construct a string of length n where the members of the string
  32.     are letters and the number of occurrence of each letter is
  33.     according to the probability of letter occurrence. The "space"
  34.     character of course part of the alphabet.
  35.  
  36.     For example: consider the character set consists of letter
  37.     A (30%), B (20%), C (40%), space (10%). Choose n = 200 (icon
  38.     is very good in handling super long string), then the number
  39.     of A's will be 60 characters, B's 40 characters, C's 80 characters,
  40.     and spaces 20 characters.
  41.  
  42.     Such a string may look (keep in mind that the characters have been
  43.     distributed using random permutation - cf. Floyd's algorithm for
  44.     random permutation):
  45.  
  46.     BAA CACCB AA CBCCAB .......
  47.  
  48. (2) Repeat as many times as the length of the random text that need to
  49.     be generated:
  50.  
  51.     Produce a random number i between 1 and n (200 in the above example)
  52.     and print string[i:i+1]
  53.  
  54. Floyd's algorithm of generating random permutation from 1 to n:
  55.  
  56. (1) Fill an array L such that L[i] := i
  57. (2) every i := n to 2 by -1 do {
  58.     t := ?i    #  generate a random index between 1 to i
  59.     L[i] :=: L[t]   # exchange the t-th element with the last
  60.             # element in current sublist
  61.     }
  62.  
  63. I think the above method is quite efficient since the distribution of 
  64. the character is done once.
  65.  
  66. -eka-
  67.